/** 随机生成网格 */
function createRandomGrids(row: number, col: number, kind: number): number[][] {
    const total = row * col;
    if (total % 2 !== 0) throw new Error("格子总数必须为偶数才能成对生成");

    // 生成成对图标数组
    const icons: number[] = [];
    for (let i = 0; i < total / 2; i++) {
        const value = Math.floor(Math.random() * kind) + 1;
        icons.push(value, value); // 成对加入
    }

    // 打乱顺序
    for (let i = icons.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [icons[i], icons[j]] = [icons[j], icons[i]];
    }

    // 填充网格
    const grids: number[][] = Array.from({ length: row }, () => Array.from({ length: col }, () => 0));
    let idx = 0;
    for (let y = 0; y < row; y++) {
        for (let x = 0; x < col; x++) {
            grids[y][x] = icons[idx++];
        }
    }

    return grids;
}

/** 彩色打印网格 */
function logGrid(grids: number[][]) {
    // 先找最大位数
    const maxLen = Math.max(...grids.flat().map(num => String(num).length));
    // 打印网格
    grids.forEach(row => {
        console.log(
            row.map(num => {
                const padded = String(num).padStart(maxLen, "0"); // 左侧填空格
                return `\x1b[9${num % 8}m${padded}\x1b[0m`; // num % 8 避免颜色码越界
            })
            .join(" ")
        );
    });
}

/** 检查是否能连接 */
function canLink(inputGrids: number[][], row1: number, col1: number, row2: number, col2: number): {success: boolean, line: string[]}{
    const line: string[] = [];
    if(!Number.isInteger(row1) || !Number.isInteger(col1) || !Number.isInteger(row2) || !Number.isInteger(col2)) return {success: false, line};
    if(row1 < 0 || row1 >= inputGrids.length || col1 < 0 || col1 >= inputGrids[0].length || row2 < 0 || row2 >= inputGrids.length || col2 < 0 || col2 >= inputGrids[0].length) return {success: false, line};
    if(inputGrids[row1][col1] !== inputGrids[row2][col2]) return {success: false, line};
    if(row1 === row2 && col1 === col2) return {success: false, line};

    const rowlen = inputGrids.length + 2
    const collen = inputGrids[0].length + 2
    
    interface Node {
        value: number; // 点的值
        point: string; //当前点 "x_y"
        turns: number; // 转弯次数
        direction: number | null; // 方向 0:上 1:右 2:下 3:左
        lastPoint?: string | null; // 上一个点 "x_y"
    }
    const map: Map<string, Node> = new Map(); //bfs图
    const grids: number[][] = Array.from({ length: rowlen }, () => Array.from({ length: collen }, () => 0));
    grids.forEach((row, raw) => {
        row.forEach((_, col) => {
            if (raw === 0 || raw === rowlen - 1 || col === 0 || col === collen - 1) grids[raw][col] = 0
            else grids[raw][col] = inputGrids[raw-1][col-1];

            map.set(`${raw}_${col}`,{
                point: `${raw}_${col}`,
                value: grids[raw][col],
                turns: 999,
                direction: null,
                lastPoint: null,
            } as Node)
        });
    });
    const begin = `${row1+1}_${col1+1}`
    const end = `${row2+1}_${col2+1}`
    map.get(begin)!.turns = 0;

    const queue: string[] = [begin];
    const visited: Set<string> = new Set([begin]);
    while(queue.length > 0){
        const current = queue.shift()!;
        visited.add(current);
        if(current === end){
            let currentNode = current;
            while(currentNode !== begin){
                const node = map.get(currentNode)!;
                line.push(node.point.split("_").map(item => Number(item) - 1).join("_"));
                currentNode = node.lastPoint!;
            }
            line.push(begin.split("_").map(item => Number(item) - 1).join("_"));
            line.reverse();
            return {success: true, line};
        }
        const currentNode = map.get(current)!;
        const row = parseInt(current.split("_")[0])
        const col = parseInt(current.split("_")[1])
        const next1 = `${row - 1}_${col}`
        const next2 = `${row + 1}_${col}`
        const next3 = `${row}_${col - 1}`
        const next4 = `${row}_${col + 1}`
        const nexts = [next1, next2, next3, next4];
        
        nexts.forEach((next, index) => { // index视为下一个点的方向 0上 1下 2左 3右
            const row = parseInt(next.split("_")[0])
            const col = parseInt(next.split("_")[1])
            if(row >= rowlen || row < 0 || col >= collen || col < 0) return
            if(!visited.has(next) && grids[row][col] === 0 || next === end){
                const nextNode = map.get(next)!;
                const isTurn = currentNode.direction !== null && currentNode.direction !== index // 是否发生了转向
                const turns = isTurn ? currentNode.turns + 1 : currentNode.turns;
                if(turns < nextNode.turns && turns <= 2){
                    queue.push(next);
                    nextNode.turns = turns;
                    nextNode.lastPoint = current;
                    nextNode.direction = index;
                }
            }
        })
    }
    return {success: false, line};
}


export default {
    createRandomGrids,
    logGrid,
    canLink
};

export { logGrid, canLink };
